package com.arong.arongHashMap.main;


import javax.swing.tree.TreeNode;
import java.io.Serializable;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Function;

public class ArongHashMap<K, V> {
    /**
     * 底层存储的数组
     */
    transient Node<K, V>[] table;

    /**
     * 调用 entrySet() 方法之后的缓存
     */
    transient Set<Map.Entry<K, V>> entrySet;

    /**
     * key-value 的键值对数量
     */
    transient int size;

    /**
     * 修改数量
     */
    transient int modCount;

    /**
     * size 超过 threshold 会进行扩容
     */
    int threshold;

    /**
     * 扩容因子
     */
    final float loadFactor;

    static class Node<K, V> implements Map.Entry<K, V> {
        /**
         * 哈希值
         */
        final int hash;

        /**
         * key
         */
        final K key;

        /**
         * VALUE 值
         */
        V value;

        /**
         * 下一个节点
         */
        Node<K,V> next;

        Node(int hash, K key) {
            this.hash = hash;
            this.key = key;
        }

        public Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        @Override
        public K getKey() {
            return this.key;
        }

        @Override
        public V getValue() {
            return this.value;
        }

        @Override
        public V setValue(V value) {
            return this.value = value;
        }


    }

    class TreeNode<K, V> extends Node<K, V> {
        public TreeNode<K,V> prev;

        TreeNode(int hash, K key) {
            super(hash, key);
        }

        public TreeNode(int hash, K key, V value, Node<K, V> next) {
            super(hash, key, value, next);
        }

        /**
         * // 转换成树节点，不去过度深究
         * @param kvArongHashMap
         * @param tab
         * @param hash
         * @param key
         * @param value
         * @return
         */
        public Node<K,V> putTreeVal(ArongHashMap<K, V> kvArongHashMap, Node<K, V>[] tab, int hash, K key, V value) {

            return null;
        }

        /**
         * 树的分裂
         * @param kvArongHashMap
         * @param newTab
         * @param j
         * @param oldTab
         */
        public void spilt(ArongHashMap<K, V> kvArongHashMap, Node<K, V>[] newTab, int j, Node<K, V>[] oldTab) {
        }

        @Override
        public K getKey() {
            return null;
        }

        @Override
        public V getValue() {
            return null;
        }

        @Override
        public V setValue(V value) {
            return null;
        }

        /**
         * 树化方法
         * @param tab
         */
        public void treeify(Node<K, V>[] tab) {
        }

        public Node<K,V> getTreeNode(int arongHash, Object key) {
            return null;
        }

        public void removeTreeNode(ArongHashMap<K, V> kvArongHashMap, Node<K, V>[] tab, boolean movable) {
        }
    }

    /**
     * 默认初始化容量 16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    /**
     * 默认加载因子为 0.75
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 构造方法1：只初始化了负载因子，底层数组采用延迟初始化
    public ArongHashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; //
    }

    // 构造方法2：自定义初始化容量和负载因子
    /**
     * 最大容量为2 ^ 30
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    public ArongHashMap(int initialCapacity, float loadFactor) {
        // 参数校验
        if(initialCapacity < 0) {
            throw new IllegalArgumentException("容量不能小于0，设置容量为" + initialCapacity);
        }

        if(initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        }

        // Float.isNaN(0.0 / 0.0) = true
        if(loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("不合法的loadFactor， loadFactor=" + loadFactor);
        }
        // 设置 loadFactor
        this.loadFactor = loadFactor;
        // 计算 threshold *
        this.threshold = tableSizeFor(initialCapacity);
    }

    /**
     * 返回大于输入参数且最近的2的整数次幂，位运算
     * 1. resize 扩容中，始终需要保持hashmap的容量为 2 ^ N
     * 2. 在分配数据位置时候，当 n = 2 ^ N, (n - 1) & hash == hash % (n - 1)
     *      运用 & 操作性能会更高
     * 输入 10 => 16; 输入 5 => 8
     * @param cap
     * @return
     */
    private int tableSizeFor(int cap) {
        // 让最高位 1 后面的数字全部变成 1; int 只有 32 位，所以移动16次即可
        // -1 的目的是让他大于等于原值，移动后会增加
        // int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        // 两个非法n值的判断，最后要加上1，因为前面减去了1
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    // 构造方法3：内部调用 HashMap(int initialCapacity, float loadFactor) 构造方法
    public ArongHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    public ArongHashMap(Map<? extends K, ? extends V> m) {
        // 设置默认负载因子
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        // 批量添加到 table 中
        putMapEntries(m, false);
    }

    private void putMapEntries(Map<? extends K,? extends V> m, boolean evict) {
        int s = m.size();
        if(s > 0) {
            // 没有完成初始化，属于构造方法
            if(table == null) {
                // 根据容量和负载因子，计算出最小需要的 table 大小， +1是因为后面会向下取整
                float ft = ((float) s / loadFactor) + 1.0F;
                // 最小需要的 table 大小
                int t = ((ft < (float) MAXIMUM_CAPACITY) ?
                        (int) ft : MAXIMUM_CAPACITY);
                // 如果大于阈值，那么需要重新计算大小
                if(t > threshold) {
                    threshold = tableSizeFor(t);
                }
            } else { // 已经初始化完成，需要扩容到阈值超过s
                while(s > threshold && table.length < MAXIMUM_CAPACITY) {
                    resize(); // 扩容
                }
            }
            // 遍历 map 集合，逐个添加元素到 hashmap 中
            for(Map.Entry<? extends K,? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(arongHash(key), key, value, false, evict);
            }
        }
    }


    static final int arongHash(Object key) {
        int h;
        // 扰动函数，高半区和低半区做异或，混合原始哈希码的高位和低位，加大低位的特征性
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    public void put(K key, V value) {
        putVal(arongHash(key), key, value, false, true);
    }

    /**
     * 插入元素
     * @param hash 哈希值
     * @param key
     * @param value
     * @param onlyIfAbsent 是否允许被修改
     * @param evict 驱逐策略 目前使用不到
     */
    final void putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K, V>[] tab; // table数组
        Node<K, V> p; // 对应位置的节点元素
        int n; // 数组大小
        int i; // 对应table的位置
        // 1. 先判断是否已经初始化，或者容量是否为0，没有的话进行扩容
        if((tab = table) == null || (n = tab.length) == 0) {
            n = (tab = resize()).length;
        }
        // 2， 创建节点
        // a. 对应的哈希值的数组索引为空
        // b. 存在哈希碰撞 --- 是否添加的 key 在原始结构中已经存在， 数组， 红黑树
        // a. 对应位置为空
        if((p = tab[i = (n - 1) & hash]) == null) {
            tab[i] = newNode(hash, key, value, null);
        } else {
            // b. 存在哈希碰撞的情况
            Node<K, V> e; // 原始节点
            K k;
            if(p.hash == hash && // 产生哈希碰撞
                    ((k = p.key) == key || (key != null && key.equals(k)))) {
                // (1). key 发现相等了（基本数据类型和引用数据类型）
                e = p;
            }
            else if(p instanceof TreeNode) {
                // (2). 找到的是红黑树节点，添加到树中
                e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
            } else {
                // (3). 链表节点情况
                for(int binCount = 0; ;++binCount) {
                    if((e = p.next) == null) {
                        // 已经判断了最开始的 p 节点，从他的 next 开始判断，为空则增加节点
                        p.next = newNode(hash, key, value, null);
                        if(binCount >= TREEIFY_THRESHOLD - 1) {
                            treeifyBin(tab, hash);
                            break;
                        }
                        // 如果遍历的 e 节点，就是要找的，则则直接使用即可
                        if (e.hash == hash &&
                                ((k = e.key) == key || (key != null && key.equals(k))))
                            break; // 结束
                        // p 指向下一个节点
                        p = e;
                    }
                }
                // 找到了对应的节点，进行修改
                if(e != null) {
                    V oldValue = e.value;
                    // 允许被修改的话, 修改节点
                    if(onlyIfAbsent || oldValue == null) {
                        e.value = value;
                    }
                }
                // 3. 善后工作
                // 增加修改次数
                modCount++;
                // 超过阈值则扩容
                if(++size > threshold) {
                    resize();
                }
            }
        }
    }

    /**
     * 当 key 不存在时，添加 key-value 键值对
     * @param key
     * @param value
     */
    public void putIfAbsent(K key, V value) {
        // 主要区别在 onlyIfAbsent 属性中
        putVal(arongHash(key), key, value, true, true);
    }


    /**
     * 创建新节点 直接返回构造方法即可
     * @param hash
     * @param key
     * @param value
     * @param next
     * @return
     */
    Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
        return new Node(hash, key, value, next);
    }

    /**
     * 所需最小链表长度
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 允许树化最小键值对个数
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
    /**
     * 树化
     * @param tab
     * @param hash
     */
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index;
        Node<K, V> e;
        // 如果未初始化或者数组容量小于64，选择扩容
        if(tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
            resize();
        } else if((e = tab[index = (hash & (n - 1))]) != null) {
            // 正式开始树化
            TreeNode<K, V> hd = null, tl =null;
            do{
                TreeNode<K, V> p = replacementTreeNode(e, null);
                if(tl == null) {
                    hd = p;
                } else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while((e = e.next) != null);
            // 树化
            if((tab[index] = hd) != null) {
                hd.treeify(tab);
            }
        }
    }
    // 该方法只是调用了TreeNode类的构造方法，依据当前节点信息构造一个树节点对象
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }

    /**
     * 扩容方法
     * 用于真正扩容和初始化数组
     */
    final Node<K, V>[] resize() {
        Node<K, V>[] oldTab = table;
        // 区别初始化还是扩容
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        // 1. 非空情况
        if(oldCap > 0) {
            if(oldCap >= MAXIMUM_CAPACITY) {
                // 超过最大容量则直接设置为阈值
                threshold = Integer.MAX_VALUE;
                return oldTab;
            } else if
            // 条件1 保证扩容后不溢出容量
                    // 条件2 当前容量大于默认值，意思是不是初始化阶段而是扩容阶段
            ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                        oldCap >= DEFAULT_INITIAL_CAPACITY) {
                newThr = oldThr << 1; // 扩容为双倍
            }
        } else if(oldThr > 0) { // 2. 已经到了为空的情况了 初始化
            // 非默认方式，oldThr 大于 0 ，则使用 oldThr 作为新的容量
            newCap = oldThr;
        } else {
            // 默认方式，oldThr 等于 0，直接赋 8，0.75 的默认值
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 如果上述的逻辑只完成了容量初始化，新的阈值没有计算，则使用负载因子计算一直
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            // 校验有无超出容量
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
        }
        // 全部赋值
        this.threshold = newThr;
        Node<K, V>[] newTab = (Node<K,V>[])new Node[newCap];
        this.table = newTab;
        // 2. 将老数组元素搬运到新数组中
        if(oldTab != null) {
            for(int j = 0; j < oldCap; ++j) {
                Node<K, V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // a. 如果该数组上链表只有一个节点，直接搬运
                    if (e.next == null) {
                        newTab[e.hash & (newCap - 1)] = e;
                    } else if (e instanceof TreeNode) {
                        // b. 是红黑树节点，通过分裂处理
                        ((TreeNode<K, V>) e).spilt(this, newTab, j, oldTab);
                    } else {
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            // 分成高位低位两条，同一个节点中链表分裂只会有 i，i + len 两种结果
                            // 那么决定他们的区别就是被抹去的位置，hash & (n - 1) 的时候，n位的数据是被抹去的了
                            // next 指向下一个节点
                            next = e.next;
                            // 满足低位
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            // 满足高位
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 设置低位到新的 newTab 的 j 位置上
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 设置高位到新的 newTab 的 j + oldCap 位置上
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

    /**
     * 添加多个元素
     * @param m
     */
    public void putAll(Map<? extends K, ? extends V> m) {
        putMapEntries(m, true);
    }

    /**
     * 移除单个元素
     * @param key
     * @return
     */
    public V remove(Object key) {
        Node<K, V> e;
        return (e = removeNode(arongHash(key), key, null, false, false)) == null ? null : e.value;
    }

    /**
     * 移除节点方法
     * @param arongHash 对应节点的哈希值
     * @param key 键
     * @param value 值
     * @param matchValue 是否需要比对值，如果为 true 只有相等的时候才会移除节点
     * @param movable 是否加锁，决定了移除的时候其他节点能不能进行移除,与红黑树删除操作相关
     * @return
     */
    final Node<K, V> removeNode(int arongHash, Object key, Object value, boolean matchValue, boolean movable) {
        Node<K, V>[] tab; // table 数组
        Node<K, V> p; // hash对应table位置的节点
        int n, index;
        // 找到了对应的 table 位置的 p 节点
        if((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & arongHash]) != null) {
            Node<K, V> node = null, e;
            K k; V v;
            // 找到 p 节点，就是要找的，直接使用即可
            if(p.hash == arongHash &&
                    ((k = p.key) == key || (key != null && key.equals(k)))) {
                node = p;
            } else if((e = p.next) != null) {
                if(p instanceof TreeNode) {
                    // 红黑树节点
                    node = ((TreeNode<K, V>)p).getTreeNode(arongHash, key);
                } else {
                    do {
                        // e 节点链表，需要遍历进行查找
                        if(e.hash == arongHash &&
                                ((k = e.key) == key || (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e; // 不断递进找到节点
                    } while((e = e.next) != null);
                }
            }
            // 找到 node 节点，进行移除
            if(node != null && (!matchValue ||(v = node.value) == value || (value != null && value.equals(v)))) {
                // 如果找到的 node 节点，是红黑树 Node 节点，则直接在红黑树中删除
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                    // 如果查找到的是链表的头节点，则直接将 table 对应位置指向 node 的下一个节点，实现删除
                else if (node == p)
                    tab[index] = node.next;
                    // 如果查找到的是链表的中间节点，则将 p 指向 node 的下一个节点，实现删除
                else
                    p.next = node.next;
                // 增加修改次数
                ++modCount;
                // 减少 HashMap 数量
                --size;
                // 返回 node
                return node;
            }
        }
        return null;
    }

    /**
     * 查找单个元素
     * @param key 元素的键
     * @return 值
     */
    public V get(Object key) {
        Node<K, V> e;
        return (e = getNode(arongHash(key), key)) == null ? null : e.getValue();
    }

    /**
     * 根据键获取或者返回默认值
     * @param key 键
     * @param defaultValue 默认值
     * @return
     */
    public V getOrDefault(Object key, V defaultValue) {
        Node<K, V> e;
        return (e = getNode(arongHash(key), key)) == null ? defaultValue : e.value;
    }

    /**
     * 是否包含某个元素
     * @param key 键
     * @return
     */
    public boolean containsKey(Object key) {
        return getNode(arongHash(key), key) != null;
    }

    /**
     * 查找单个元素
     * @param hash 元素的哈希值
     * @param key 元素的键
     * @return
     */
    private Node<K,V> getNode(int hash, Object key) {
        Node<K, V>[] tab;
        Node<K, V> first, e;
        int n;
        K k;
        // 查找哈希值对应的 table 上的节点
        if((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
            // 只有一个：直接用
            if(first.hash == hash &&
                    ((k = first.key) == key || (key != null && key.equals(k)))) {
                return first;
            }
            // 有多个的情况
            if((e = first.next) != null) {
                // 是红黑树节点，在红黑树中查找
                if(first instanceof TreeNode) {
                    return ((TreeNode<K, V>)first).getTreeNode(hash, key);
                }
                // 是node节点，需要遍历进行查找
                do {
                    if(e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k)))) {
                        return e;
                    }
                } while((e = e.next) != null);
            }

        }
        return null;
    }

    /**
     * 判断是否包含值
     * @param value 值
     * @return
     */
    public boolean containsValue(Object value) {
        Node<K, V>[] tab;
        V v;
        // 浅浅进行一个非空校验
        if((tab = table) != null && size > 0) {
            // 遍历 table 数组 (数组 -> 节点 -> 链表的逐步向下变化)
            for(Node<K, V> e: tab) {
                for(; e != null; e = e.next) {
                    if((v = e.value) == value || (value != null && value.equals(v))) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    /**
     * 将键转换成为数组
     * @param a entry 的集合
     * @return key 的集合
     * @param <T> entry 的类型
     */
     <T> T[] keysToArrays(T[] a) {
         Node<K, V>[] tab;
        int idx = 0;
        if(size > 0 && (tab = table) != null) {
            // 遍历 table 数组
            for(Node<K, V> e: tab) {
                // 逐步遍历每个节点
                for(; e != null; e = e.next) {
                    ((Object[]) a)[idx++] = e.key;
                }
            }
        }
        return a;
     }

    /**
     * 将值转换成为数组
     * @param a entry 的集合
     * @return value 的集合
     * @param <T> entry 的类型
     */
    <T> T[] valuesToArray(T[] a) {
        Node<K,V>[] tab;
        int idx = 0;
        if (size > 0 && (tab = table) != null) {
            // 遍历 table 数组
            for (Node<K,V> e : tab) {
                // 遍历链表或红黑树
                for (; e != null; e = e.next) {
                    // 逐个设置 value 到 r 数组中
                    ((Object[]) a)[idx++] = e.value;
                }
            }
        }
        // 返回
        return a;
    }

    transient Set<K> keySet;

    /**
     * 获取键的集合，关键设置了在于缓存
     * @return
     */
    public Set<K> keySet() {
        // 获得 keySet 缓存
        Set<K> ks = keySet;
        // 如果不存在，则进行创建
        if (ks == null) {
            // ks = new KeySet(); 这里是 AbstractSet 的内部类，新建一个 KeySet 对象
            keySet = ks;
        }
        return ks;
    }

    // HashMap.java


    /**
     * 获取键值对集合
     * @return
     */
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es = entrySet;
        // 获得 entrySet 缓存
        // 如果不存在，则进行创建
        if(es == null) {
        // entrySet = new EntrySet(); 这里是 AbstractSet 的内部类，新建一个 EntrySet 对象
            return entrySet;
        }
        return es;
    }

    /**
     * 清空 hashMap
     */
    public void clear() {
        Node<K,V>[] tab;
        // 增加修改次数
        modCount++;
        if ((tab = table) != null && size > 0) {
            // 设置大小为 0
            size = 0;
            // 设置每个位置为 null
            for (int i = 0; i < tab.length; ++i)
                tab[i] = null;
        }
    }

    /**
     * 旧值替换新值，多了一个旧值对比的操作
     * @param key 键
     * @param oldValue 旧值
     * @param newValue 新值
     * @return
     */
    public boolean replace(K key, V oldValue, V newValue) {
        ArongHashMap.Node<K,V> e; V v;
        if ((e = getNode(arongHash(key), key)) != null &&
                ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
            e.value = newValue;
            // afterNodeAccess(e); 主要是运用于 linkHashMap 中
            return true;
        }
        return false;
    }

    /**
     * 旧值替换新值
     * @param key 键
     * @param value 值
     * @return
     */
    public V replace(K key, V value) {
        ArongHashMap.Node<K,V> e;
        if ((e = getNode(arongHash(key), key)) != null) {
            V oldValue = e.value;
            e.value = value;
            // afterNodeAccess(e); 主要是运用于 linkHashMap 中
            return oldValue;
        }
        return null;
    }


    /**
     * 如果该 key 不存在的话，将计算后的结果作为 value 加入函数
     * 如果 key 存在，返回该值，是新增和查找操作的结合
     * @param key 键
     * @param mappingFunction 重新映射函数 主要起到了计算的作用
     * @return
     */
    public V computeIfAbsent(K key,
                             Function<? super K, ? extends V> mappingFunction) {
        if (mappingFunction == null)
            throw new NullPointerException();
        int hash = arongHash(key);
        Node<K,V>[] tab; Node<K,V> first; int n, i;
        int binCount = 0;
        TreeNode<K,V> t = null;
        Node<K,V> old = null;
        // 因为是新增操作，所以扩容的判断是需要的 判断一个容量够不够，一个有没有初始化完成
        if (size > threshold || (tab = table) == null ||
                (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 找得到节点
        if ((first = tab[i = (n - 1) & hash]) != null) {
            // 节点是红黑树
            if (first instanceof TreeNode)
                old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
            else {
                // 节点是数组，逐个遍历寻找
                Node<K,V> e = first; K k;
                do {
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k)))) {
                        old = e;
                        break;
                    }
                    ++binCount;
                } while ((e = e.next) != null);
            }
            V oldValue;
            // 能够根据 key 查找到对应的值，则返回该值即可
            if (old != null && (oldValue = old.value) != null) {
                // afterNodeAccess(old); 主要是运用于 linkHashMap 中
                return oldValue;
            }
        }
        // 函数式编程，计算值
        V v = mappingFunction.apply(key);
        if (v == null) {
            return null;
        } else if (old != null) {
            old.value = v;
            // afterNodeAccess(old); 主要是运用于 linkHashMap 中
            return v;
        }
        else if (t != null)
            // 该节点已经是树状的情况
            t.putTreeVal(this, tab, hash, key, v);
        else {
            tab[i] = newNode(hash, key, v, first);
            if (binCount >= TREEIFY_THRESHOLD - 1)
                treeifyBin(tab, hash);
        }
        ++modCount;
        ++size;
        // afterNodeInsertion(true); 主要是运用于 linkHashMap 中
        return v;
    }

    /**
     * 查找函数，如果不存在，返回null
     * 如果存在，返回计算后的值
     * @param key 键
     * @param remappingFunction 重新映射函数
     * @return
     */
    public V computeIfPresent(K key,
                              BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        // 必须有计算函数，因为需要返回值
        if (remappingFunction == null)
            throw new NullPointerException();
        Node<K,V> e; V oldValue;
        int hash = arongHash(key);
        if ((e = getNode(hash, key)) != null &&
                (oldValue = e.value) != null) {
            // 查找到值，开始根据旧值和 key 进行计算返回结果
            V v = remappingFunction.apply(key, oldValue);
            if (v != null) {
                e.value = v;
                // afterNodeAccess(e); 主要是运用于 linkHashMap 中
                return v;
            }
            else
                // 不存在的时候帮忙做了一次 key 对应的 value 为 null 的 gc
                removeNode(hash, key, null, false, true);
        }
        return null;
    }

    /**
     * 计算 修改或者新增操作
     * 当 key 不存在时，是新增操作
     * 当 key 存在时，根据函数表达式去修改对应的 value
     * @param key 键
     * @param remappingFunction 函数表达式
     * @return
     */
    public V compute(K key,
                     BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        // 必须有计算函数，因为需要返回值
        if (remappingFunction == null)
            throw new NullPointerException();
        int hash = arongHash(key);
        Node<K,V>[] tab; Node<K,V> first; int n, i;
        int binCount = 0;
        TreeNode<K,V> t = null;
        Node<K,V> old = null;
        // 因为可能有新增操作，所以需要进行扩容
        if (size > threshold || (tab = table) == null ||
                (n = tab.length) == 0)
            n = (tab = resize()).length;
        // key 查找到值了
        if ((first = tab[i = (n - 1) & hash]) != null) {
            if (first instanceof TreeNode)
                // 是树的情况
                old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
            else {
                // 是节点的情况
                Node<K,V> e = first; K k;
                do {
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k)))) {
                        old = e;
                        break;
                    }
                    ++binCount;
                } while ((e = e.next) != null);
            }
        }
        V oldValue = (old == null) ? null : old.value;
        // 根据函数计算
        V v = remappingFunction.apply(key, oldValue);
        if (old != null) {
            if (v != null) {
                // 完成 compute 操作，将计算的值赋予旧值
                old.value = v;
                // afterNodeAccess(old); 主要是运用于 linkHashMap 中
            }
            else
                removeNode(hash, key, null, false, true);
        }
        else if (v != null) {
            // 函数计算出来的值不为空是必要的条件，也就是其实属于 old == null 的情况
            if (t != null)
                // 树的情况
                t.putTreeVal(this, tab, hash, key, v);
            else {
                // 链表的情况
                tab[i] = newNode(hash, key, v, first);
                if (binCount >= TREEIFY_THRESHOLD - 1)
                    treeifyBin(tab, hash);
            }
            ++modCount;
            ++size;
            // afterNodeInsertion(true); 主要是运用于 linkHashMap 中
        }
        return v;
    }


    public V merge(K key, V value,
                   BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
        if (value == null)
            throw new NullPointerException();
        if (remappingFunction == null)
            throw new NullPointerException();
        int hash = arongHash(key);
        Node<K,V>[] tab; Node<K,V> first; int n, i;
        int binCount = 0;
        TreeNode<K,V> t = null;
        Node<K,V> old = null;
        // 扩容新增
        if (size > threshold || (tab = table) == null ||
                (n = tab.length) == 0)
            n = (tab = resize()).length;
        // key 查找到值了
        if ((first = tab[i = (n - 1) & hash]) != null) {
            if (first instanceof TreeNode)
                // 树的情况
                old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
            else {
                // 节点的情况
                Node<K,V> e = first; K k;
                do {
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k)))) {
                        old = e;
                        break;
                    }
                    ++binCount;
                } while ((e = e.next) != null);
            }
        }

        if (old != null) {
            V v;
            // 有旧值
            if (old.value != null)
                // 将旧值和所给的值进行计算
                v = remappingFunction.apply(old.value, value);
            else
                v = value;
            if (v != null) {
                old.value = v;
                // afterNodeAccess(old); 主要是运用于 linkHashMap 中
            }
            else
                // 计算不出来值，做个 gc
                removeNode(hash, key, null, false, true);
            return v;
        }
        // 计算出来值了，加值
        if (value != null) {
            if (t != null)
                // 树的情况
                t.putTreeVal(this, tab, hash, key, value);
            else {
                // 节点的情况
                tab[i] = newNode(hash, key, value, first);
                if (binCount >= TREEIFY_THRESHOLD - 1)
                    treeifyBin(tab, hash);
            }
            ++modCount;
            ++size;
            // afterNodeInsertion(true); 主要是运用于 linkHashMap 中
        }
        return value;
    }
}
